package com.data.basic.chapter08;

import com.data.basic.chapter02.Array;
import sun.tools.jar.*;

/** 用自定义的数组实现完全二叉树（最大堆）的存储
 * 最大堆的定义：
 * Created by wangbing on 2018/5/21.
 */
public class MaxHeap<E extends Comparable> {

    private Array<E> data;

     public MaxHeap (int capacity){
        data = new Array<E>(capacity);

    }

    /**
     * heapify的过程
     * @param arr
     */
    public MaxHeap(E[] arr){
        data = new Array<E>(arr);
        for (int i=parent(arr.length-1);i>=0;i--){
            siftDown(i);
        }
    }

    public MaxHeap() {
        data = new Array<E>();
    }


    // 返回堆中的元素
    public int size(){
        return data.getSize();
    }

    // 返回一个布尔值，表示堆是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示，一个索引所表示元素的父亲节点的索引
    private int parent(int index){
        if (index == 0) {

        throw new IllegalArgumentException("index-0  doesn't have parent!");
        }
        return (index-1)/2;
    }

    // 返回完全二叉树的数组表示，一个索引所表示元素的左孩子节点的索引
    private int leftChild(int index){
//        if (index==(data.getSize()-1)){
//            throw new IllegalArgumentException("index-last  doesn't have left child!");
//        }
        return index*2+1;
    }
    // 返回完全二叉树的数组表示，一个索引所表示元素的右孩子节点的索引
    private int rightChild(int index){
//        if (index==(data.getSize()-1)){
//            throw new IllegalArgumentException("index-last  doesn't have right child!");
//        }
        return index*2+2;
    }


    /**
     * 向堆中添加元素
     */
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }

    private void siftUp(int k) {
        while(k>0&&data.get(parent(k)).compareTo(data.get(k))<0){
            data.swap(k,parent(k));
            // 更新需要对比的数组下标
            k = parent(k);
        }
    }
    /**
     * 查看堆中最大元素
     */
    public E findMax(){
        if (data.getSize()==0){
            throw new IllegalArgumentException("cannot find max   when heap is empty!");

        }
        return data.get(0);
    }

    /**
     * 从堆中删除元素
     */
    public E extractMax(){
        E ret = findMax();
        // 完成元素的交换
        data.swap(0,data.getSize()-1);
        data.removelast();
        // 最大堆的调整

        siftDown(0);


        return ret;
    }

    private void siftDown(int k) {


        // 当左孩子的索引越界了，就停止；因为右孩子对应的数组下标大于左孩子的数组下标
        while (leftChild(k)<data.getSize()){

            int j = leftChild(k);
            if (j+1<data.getSize() && data.get(j+1).compareTo(data.get(j))>0){
           // 此时data[j] 是left child和right child中最大值
                // 或者j++
                j = rightChild(k);


            }
            if (data.get(k).compareTo(data.get(j))>=0){
                break;

            }
            data.swap(k,j);
            k = j;



        }

    }


    /**
     * 取出堆中的最大元素
     */
public E replace(E e){
    E ret = findMax();
    data.set(0,e);
    siftDown(0);
    return ret;

}

}
